This invention relates to a method and an apparatus for optimizing the placement and shape of blocks in a top down manner at an initial stage of the automatic layout design of a VLSI or an IC.
The following four methods are known. The first known method is to minimize the overlap between blocks, the wiring lengths, and the chip size by successively repeating the operation of moving the blocks toward each other, the operation of moving the blocks away from each other, and the operation of modifying the boundary shapes of the blocks. In the first known method, since only a single structure of the routing area or a single channel structure is estimated until the optimal combination of the block shape is determined, it tends to be difficult to attain acceptable optimization.
The second known method is to optimize the block shapes for each channel structure by expressing a given circuit in a graph, determining its plane drawing, and finally listing the rectangular dual graphs of the plane drawing which correspond to the respective channel structures. In cases where it is difficult to obtain the plane drawing directly from the graph, edges are deleted from the graph and vertices are added to the graph to derive the plane drawing of the graph. The second known method has the function of searching many channel structures on the basis of connections in the circuit expressed in the plane graph. In the second known method, the processing tends to be complicated and the number of the listed channel structures increases exponentially with the number of the blocks. In addition, since the placement of the blocks which are being processed is undetermined, it is difficult to estimate the wiring areas between the blocks.
In the third known method, the structure of the placement of blocks is represented by binary trees, and the placement conditions or the channel structures are searched through steps such as a step of exchanging the positions of adjacent blocks by changing the binary trees. The third known method includes a simulated annealing method (see U.S. Pat. No. 4,495,559) used in the search of the placement conditions. In the third known method, since a very large number of channel structures are listed and even ineffective channel structures are listed, the necessary calculation time tends to be long. In addition, since the placement of the blocks which are being processed is undetermined, it is difficult to estimate the wiring areas between the blocks.
The fourth known method includes a clustering method which is used to form a hierarchical structure in a bottom up manner to make a floor plan process hierarchical. After the hierarchical structure is formed, the template of the floor plan applied for each hierarchy level is searched in a top down manner to attain the optimization. The fourth known method resolves the problem of the third known method that the number of listed channel structures is very large. However, the fourth known method does not resolve the other problem of the third known method. In the fourth known method, since the resultant optimization greatly depends on the way of the clustering, the optimization in a top down manner tends to be difficult.